Fibonacci heap
Insertion, minimum value search, key value subtraction, merge Amortization O(1) time
Deletion and minimum value deletion Amortization O(log n) time
In binary heap, the former is O(log n), so the Fibonacci heap is useful when there is a lot of processing in the former
[Fibonacci heap - Wikipedia https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E3%83%92%E3%83%BC%E3%83% 97]
---
This page is auto-translated from /nishio/フィボナッチヒープ. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.